public class Sort {
    public static void main(String[] args) {
        int[] testArray = {34, 7, 23, 32, 5, 62, 15, 22, 37, 42, 10, 19, 24, 50, 8};
        Sort.quickSort(testArray);
        for(int i = 0; i < testArray.length; i++) {
            System.out.print(testArray[i] + " ");
        }
    }

    public static void quickSort(int[] array) {
        /**
         * 快速排序*/
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int left, int right) {
        /**
         * 快速排序主体
         * */
        // 1 若是left >= right, 说明此时相遇，直接返回
        if(left >= right) {
            return;
        }
        // 2 找基准值
        int pivot = partition(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

    private static int partition(int[] array, int left, int right) {
        /**
         * 找到基准值所有的有序位置（划分数组）
         * */
        // 1 保留基准值及其下标
        int originalIndex = left;
        int target = array[originalIndex];

        // 2 在数组中找到基准值的有序位置
        // 分两个指针，left 和 right
        // 要求：基准值左边全部小于等于基准值，右边全部大于基准值
        while(left < right) {
            // -right从右至左，遇见第一个比基准值小的数停下
            while(left < right && array[right] >= target) {
                right --;
            }

            // -left从左至右，遇见第一个比基准值大的数停下
            while(left < right && array[left] <= target) {
                left ++;
            }

            // 交换
            swap(array, left, right);
        }

        // 3 出循环，找到基准值，交换并返回下标
        swap(array, originalIndex, left);
        return left;
    }

    private static void swap(int[] array, int left, int right) {
        /**
         * 交换函数
         * */
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }


}
